package com.zlk.algorithm.algorithm.sort.heap;

import org.junit.Test;

import java.lang.reflect.Array;
import java.util.*;

/**
 * @program: algorithm
 * @ClassName HeapGreater
 * @description: 加强堆实现  PriorityQueue 的底层实现 indexOf(Object o) 方法 删除找指定索引是通过遍历，效率慢
 * 加强堆采用
 * todo 处理T为基础类型
 * @author: slfang
 * @create: 2024-01-24 14:19
 * @Version 1.0
 **/
public class HeapGreater<T> {

    //加强堆内部成员变量
    // 1、T 数组 此处用ArrayList 实现
    // 2、heap size
    // 3、比较器
    // 4、反向索引表
    /**
     * 堆数据
     */
    List<T> heap ;

    /**
     * 堆容量
     */
    int heapSize ;

    /**
     * 比较器  表示修饰的都是类型T的父类，包括T自己
     * ＜? extends T＞和＜? super T＞理解与使用
     * https://blog.csdn.net/qq_41276800/article/details/130200677
     */
    Comparator<? super T> comp;

    /**
     * 反向索引表
     */
    HashMap<T,Integer> indexMap;

    public HeapGreater(Comparator<? super T> comp){
        this.comp = comp;
        indexMap = new HashMap<>();
        heapSize = 0;
        heap = new ArrayList<>();
    }

    public void add(T t){
        heap.add(t);
        //为什么现在直接放因为，后续操作 swap 有交换 indexMap 有交换对象
        indexMap.put(t,heapSize);
        heapInsert(heapSize++);
    }

    public void remove (T obj){
        //heapSize--;
        T replace = heap.get(heapSize - 1);
        int index = indexMap.get(obj);
        indexMap.remove(obj);
        heap.remove(--heapSize);

        //为什么不直接swap   也可以直接swap
        if (obj != replace) {
            heap.set(index, replace);
            indexMap.put(replace, index);
            resign(replace);
        }
    }

    public void resign(T obj) {
        heapInsert(indexOf(obj));
        heapify(indexOf(obj));
    }

    private int  indexOf(T t) {
        return indexMap.get(t);
    }

    public void heapInsert(int index){
        while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
            swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }
    private void swap( int i, int j) {
        T o1 = heap.get(i);
        T o2 = heap.get(j);
        heap.set(i, o2);
        heap.set(j, o1);
        indexMap.put(o2, i);
        indexMap.put(o1, j);
    }

    public T pop() {
        T ans = heap.get(0);
        swap(0, heapSize - 1);
        indexMap.remove(ans);
        heap.remove(--heapSize);
        heapify(0);
        return ans;
    }

    private void heapify(int index) {
        int l = 2*index+1;
        int r = l+1;
        while (l<heapSize){
            int best ;
            if(r>=heapSize){
                best = l;
            }else{
                // 任何比较器：
                // compare方法里，遵循一个统一的规范：
                // 返回正数的时候，认为第一个参数应该排在前面
                // 返回负数的时候，认为第二个参数应该排在前面
                // 返回0的时候，认为无所谓谁放前面
                //不理解看 V对象测试效果
                //默认都是从小到大排列的
                best = comp.compare(heap.get(r),heap.get(l))<0?r:l;
            }
            best = comp.compare(heap.get(best), heap.get(index)) < 0 ? best : index;
            if(best == index ){
                break;
            }
            index = best;
            l = 2*index+1;
        }
    }

    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });

        Integer integer = Integer.valueOf(2);
        Integer integer2 = Integer.valueOf(3);


        int[] arr = new int[]{1,2,3,4,5};
        for (int i : arr) {
            queue.add(i);
        }
        while (!queue.isEmpty()){
            System.out.println(queue.poll());
        }

    }

    public List<T> getAllElements() {
        List<T> ans = new ArrayList<>();
        for (T c : heap) {
            ans.add(c);
        }
        return ans;
    }

    public boolean isEmpty() {
        return heapSize == 0;
    }

    public int size() {
        return heapSize;
    }

    public boolean contains(T obj) {
        return indexMap.containsKey(obj);
    }

    public T peek() {
        return heap.get(0);
    }


}
